Computer multiplication circuits accept a multiplicand and a multiplier and generate a product. One straightforward method to multiply binary numbers is the long form of multiplication. This is the standard shift-and-add approach. That is, for each column in a multiplier, shift the multiplicand the appropriate number of columns and add the shifted multiplicand into the final total if the multiplier column contains a one, or don't add it if the if the multiplier column contains a zero. The shifted numbers to be added are called partial products because they represent intermediate results in determining the final product of the multiply. All of the partial products are added together to determine the final product. Thus, the number of shifts to be executed is equal to the number of columns in the multiplier, and the number of partial products to be added is equal to the number of ones in the multiplier.
This method of multiplying is slow and there have been methods developed to speed up the multiplying process. One method to speed up multiplying is to use radix-four multiplication or Booth multiplication. Instead of shifting and adding for every column of the multiplier, the method uses every other column. Booth encoding involves looking at three consecutive bits of a multiplier to determine whether to multiply the multiplicand by −1, +1, −2, +2, or zero to obtain a partial product. This method reduces the number of partial products to be added by one-half, and consequently reduces the complexity and power consumption of circuits that implement the method.
The Booth encoding process consists of looking at three bits of a multiplier to determine how to calculate a partial product. As an example the hexadecimal number 4E2 is shown below.010011100010—In long multiplication by the shift and add method, twelve partial products would be used to determine the final product. To determine the partial products for Booth encoding, the number is grouped into the three-bit blocks. The least significant block begins with only the two least significant bits of the multiplier and zero is used as the least significant bit (LSB) of the block. Grouping starts at the LSB and each block overlaps the previous block by one bit. The most significant block is sign extended if necessary to fill out a block. Based on the three bits in the block, the multiplicand is multiplied by −1, +1, −2, +2, or 0 to obtain the partial product. Table 1 shows the encoding used for each possible three-bit block.
TABLE 1Bit BlockPartial product000  0 * Multiplicand001+1 * Multiplicand010+1 * Multiplicand011+2 * Multiplicand100−2 * Multiplicand101−1 * Multiplicand110−1 * Multiplicand111  0 * MultiplicandStarting with the LSB in the example above, the six blocks are 100, 001, 100, 111, 001 and 010. The multiplicand is then multiplied by −2, +1, −2, 0, +1 and +1 to obtain the six partial products. The partial products are shifted according to which block is decoded and then added together to obtain the final product.
Despite reducing the number of partial products by one-half, Booth multiplication can still result in complex circuits. Typically, computers that want to obtain the result of a multiply as quickly as possible use a circuit to calculate each bit of the partial products. So, for example, a 64-bit by 64-bit multiply that uses the shift and add method needs to add 64 partial products of 64 bits each; or 4096 circuits. A 64-bit by 64-bit multiply that uses Booth encoding reduces the number of partial products to be added by one-half. However, this method still requires adding 32 partial products of 64 bits each; or 2048 circuits.
It can be seen from this discussion that reducing the complexity of multiply circuits would result in significant savings of space used in fabricating the circuits and saving of power consumption in the operation of such circuits.